翻訳と辞書 Words near each other ・ Legende ・ Legende sau basmele românilor ・ Legendele Olimpului ・ Legenden om Ljusets rike ・ LegendMUD ・ Legendo ・ Legendre ・ Legendre (crater) ・ Legendre chi function ・ Legendre form ・ Legendre function ・ Legendre polynomials ・ Legendre pseudospectral method ・ Legendre rational functions ・ Legendre relation ・ Legendre sieve ・ Legendre symbol ・ Legendre transformation ・ Legendre wavelet ・ Legendre's conjecture ・ Legendre's constant ・ Legendre's equation ・ Legendre's formula ・ Legendre's theorem on spherical triangles ・ Legendre's three-square theorem ・ Legendre–Clebsch condition ・ Legendrian knot ・ Legends (Above the Law album) ・ Legends (Beverley Craven album) ・ Legends (Bob Catley album) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Legendre sieve ： ウィキペディア英語版 Legendre sieve In mathematics, the Legendre sieve, named after Adrien-Marie Legendre, is the simplest method in modern sieve theory. It applies the concept of the Sieve of Eratosthenes to find upper or lower bounds on the number of primes within a given set of integers. Because it is a simple extension of Eratosthenes' idea, it is sometimes called the Legendre–Eratosthenes sieve.〔Iwaniec, Henryk. (The sieve of Eratosthenes-Legendre ). Annali della Scuola Normale Superiore di Pisa - Classe di Scienze, Sér. 4, 4 no. 2 (1977), p. 257-268 MR (453676 )〕 ==Legendre's identity== The central idea of the method is expressed by the following identity, sometimes called the Legendre identity: :$S(A,P)=\; \backslash sum\_\backslash sum\_\; \backslash mu(d)\; =\backslash sum\_\backslash mu(d)|A\_d|,$ where ''A'' is a set of integers, ''P'' is a product of distinct primes, $\backslash mu$ is the Möbius function, and $A\_d$ is the set of integers in ''A'' divisible by ''d'', and ''S(A, P)'' is defined to be: :$S(A,\; P)\; =\; |\backslash |$ i.e. ''S''(''A'', ''P'') is the count of numbers in ''A'' with no factors common with ''P''. Note that in the most typical case, ''A'' is all integers less than or equal to some real number ''X'', ''P'' is the product of all primes less than or equal to some integer ''z'' < ''X'', and then the Legendre identity becomes: : $$ \begin S(A,P) & = \sum_\mu(d)\left\lfloor\frac\right\rfloor \\ & = () - \sum_ \left\lfloor\frac\right\rfloor + \sum_ \left\lfloor\frac\right\rfloor - \sum_ \left\lfloor\frac\right\rfloor + \cdots \end (where $\backslash lfloor\; X\; \backslash rfloor$ denotes the floor function). In this example the fact that the Legendre identity is derived from the Sieve of Eratosthenes is clear: the first term is the number of integers below ''X'', the second term removes the multiples of all primes, the third term adds back the multiples of two primes (which were miscounted by being "crossed out twice"), and so on until all $2^$ (where $\backslash pi(z)$ denotes the number of primes below ''z'') combinations of primes have been covered. Once ''S''(''A'', ''P'') has been calculated for this special case, it can be used to bound $\backslash pi(X)$ using the expression :$S(A,P)\; \backslash geq\; \backslash pi(X)\; -\; \backslash pi(z)\; +\; 1,\; \backslash ,$ which follows immediately from the definition of ''S''(''A'', ''P''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Legendre sieve」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.